import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:岁亮亮
 * Date:2024-06-20
 * TIME:15:39
 */
public class Test {

   static class Tmp implements Comparator<Integer>{

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    }

    /***
     * 关于top- k的问题
     * 在给定的数组上 找出前 k 个最小的元素
     * 两种解法
     * 1.暴力 建立一个小根堆 出前k个就是最小的元素
     */
    public static int[] top_k(int[] array,int k){
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Tmp());
        //向上调整创建小根堆 O(N*logN)
        for (int i = 0; i < array.length; i++) {
            queue.offer(array[i]);
        }
        //出队调整堆 O(KlogN)
        int[] value = new  int[k];
        for (int i = 0; i < k; i++) {
            value[i] = queue.poll();
        }
        return value;
    }
    public static int[] top_k2(int[] array,int k){
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Tmp());
        //创建一个大根堆 大小为k O(k*logK)
        for (int i = 0; i < k; i++) {
            queue.offer(array[i]);
        }
        //遍历剩下的数组元素 若比堆顶元素小 堆顶出队元素小的入队 O((N-K)*logK)
        for (int i = k; i < array.length; i++) {
            int top = queue.peek();
            if(array[i] < top){
                queue.poll();
                queue.offer(array[i]);
            }
        }
        int[] value = new int[k];
        for (int i = 0; i < k; i++) {
            value[i] = queue.poll();
        }
        return value;

    }

    public static void main(String[] args) {
        int[] array = new int[]{27,18,10,7,8,35,28};
        int k = 3;
        int[] value = top_k2(array,k);
        System.out.println(Arrays.toString(value));
        PriorityQueue<Integer> q2 = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);//大根堆
            }
        });

    }

    public static void main1(String[] args) {
        int[] array = new int[]{1};
        Tmp tmp = new Tmp();
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Tmp());
        queue.offer(10);
        queue.offer(5);
        System.out.println(queue.poll());
    }



}
